package leetCode.offer49;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * 示例:
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 * 说明:
 * 1是丑数,n不超过1690。
 */
public class Solution2 implements Solution{

    @Override
    public int nthUglyNumber(int n) {
        int[] base = {2,3,5};
        Set<Long> seen = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        for(int i=0;i < n; i++) {
            long cur = heap.poll();
            ugly = (int) cur;
            for(int num:base) {
                long next = cur*num;
                if(seen.add(next)) heap.offer(next);
            }
        }
        return ugly;
    }

    public static void main(String[] args) {
        Solution s = new Solution2();
        long start = System.currentTimeMillis();
        System.out.println(s.nthUglyNumber(1690));
        System.out.println("耗时："+ (System.currentTimeMillis()-start)+" ms");
    }

}
